package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-19 11:19
 * @Description: HouseRobberII$213-打家劫舍2-https://leetcode-cn.com/problems/house-robber-ii/
 */
public class HouseRobberII {

	/**
	 *
	 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
	 *
	 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
	 *
	 *  
	 *
	 * 示例 1：
	 *
	 * 输入：nums = [2,3,2]
	 * 输出：3
	 * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
	 * 示例 2：
	 *
	 * 输入：nums = [1,2,3,1]
	 * 输出：4
	 * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
	 *      偷窃到的最高金额 = 1 + 3 = 4 。
	 * 示例 3：
	 *
	 * 输入：nums = [0]
	 * 输出：0
	 *  
	 *
	 * 提示：
	 *
	 * 1 <= nums.length <= 100
	 * 0 <= nums[i] <= 1000
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/house-robber-ii
	 *
	 * 【分析】
	 *  step 1 确定状态：
	 *  同HouseRobberI类似，只是现在是房子排成了一个圈
	 *  房子0和房子N-1收尾相连，当时不能同时偷盗窃
	 *      没有偷房子0时，
	 *          此时环断开，最优策略变成了对于房子1~(N-1)偷盗的最优策略
	 *
	 *      没有偷房子N-1
	 *          此时环断开，最优策略变为对于房子0~(N-2)偷到的最优策略
	 *
	 *      最后比较两者即可
	 *
	 *  step 2 状态转移方程：
	 *      f[i] = max(f[i-1],f[i-2]+A[i-1])
	 *
	 *  step 3 初始条件和边界
	 *      f[0] = 0
	 *      f[1[ = A[0]
	 *      f[2] = max{A[0],A[1]}
	 *  step 4 计算顺序
	 *
	 * 	     初始化f[0]
	 * 	     计算： f[0],f[1],f[2]...f[n]
	 *
	 * 	     结果为f[n]
	 *
	 */
	public int rob(int[] nums) {

		int n = nums.length;
		if(n == 0){
			return 0;
		}
		if(n==1){
			return nums[0];
		}

		int[] f = new int[n+1];

		f[0] = 0;
		f[1] = 0;

		int temp1,temp2;
		//不偷0,(2~n-1)

		for (int i = 2; i <= n; i++) {
			f[i] = Math.max(f[i-1],f[i-2]+nums[i-1]);
		}
		temp1 = f[n];


		f[1] = nums[0];
		// 不偷n-1,1~(n-2)
		for (int i = 2; i <= n-1; i++) {
			f[i] = Math.max(f[i-1],f[i-2]+nums[i-1]);
		}
		temp2 = f[n-1];
		// 比较大小

		return Math.max(temp1,temp2);
	}

	public static void main(String[] args) {

		int[] nums = {1};
		HouseRobberII instance = new HouseRobberII();
		System.out.println(instance.rob(nums));
	}
}
